//Given a string s, remove duplicate letters so that every letter appears once a
//nd only once. You must make sure your result is the smallest in lexicographical 
//order among all possible results. 
//
// Note: This question is the same as 1081: https://leetcode.com/problems/smalle
//st-subsequence-of-distinct-characters/ 
//
// 
// Example 1: 
//
// 
//Input: s = "bcabc"
//Output: "abc"
// 
//
// Example 2: 
//
// 
//Input: s = "cbacdcbc"
//Output: "acdb"
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 104 
// s consists of lowercase English letters. 
// 
// Related Topics 栈 贪心算法 字符串 
// 👍 522 👎 0


package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

//Java：Remove Duplicate Letters
class P316RemoveDuplicateLetters {
    public static void main(String[] args) {
        Solution solution = new P316RemoveDuplicateLetters().new Solution();
        solution.removeDuplicateLetters("bcac");
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            if (s.length() == 1) {
                return s;
            }
            //单词频数
            int[] charCount = new int[26];
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                charCount[c - 'a']++;
            }
            Deque<Character> stack = new ArrayDeque<>();
            boolean[] isVisited = new boolean[26];
            for (int i = 0; i < s.length(); i++) {
                char cur = s.charAt(i);
                charCount[cur - 'a']--;
                if (isVisited[cur - 'a']) {
                    continue;
                }
                //如果栈顶字符字典序大于当前字符，选择当前字符，考虑删除栈顶字符
                while (!stack.isEmpty() && stack.peek() > cur
                        && charCount[stack.peek() - 'a'] >= 1) {
                    Character pop = stack.pop();
                    isVisited[pop - 'a'] = false;
                }
                stack.push(cur);
                isVisited[cur - 'a'] = true;
            }
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.append(stack.pollLast());
            }
            return sb.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}